// 460.[DFS/迷宫足球] maze_football
// https://leetcode.cn/problems/the-maze
// 由空地（用 0 表示）和墙（用 1 表示）组成的迷宫 maze 中有一个球。
// 球可以途经空地向 上、下、左、右 四个方向滚动，且在遇到墙壁前不会停止滚动。
// 当球停下时，可以选择向下一个方向滚动。
// 给你一个大小为 m x n 的迷宫 maze ，以及球的初始位置 start 和目的地
// destination ， 其中 start = [startrow, startcol] 且 destination =
// [destinationrow, destinationcol] 。
// 请你判断球能否在目的地停下：如果可以，返回 true ；否则，返回 false 。
// 你可以 假定迷宫的边缘都是墙壁（参考示例）
// 输入：maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]],
// start = [0,4], destination = [4,4] 输出：true 解释：一种可能的路径是 : 左 ->
// 下 -> 左 -> 下 -> 右 -> 下 -> 右。 输入：maze =
// [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4],
// destination = [3,2] 输出：false
// 解释：不存在能够使球停在目的地的路径。注意，球可以经过目的地，但无法在那里停驻。
public
class Solution {
 public
  boolean hasPath(int[][] maze, int[] start, int[] destination) {
    boolean[][] visited = new boolean[maze.length][maze[0].length];
    return dfs(maze, start, destination, visited);
  }
 public
  boolean dfs(int[][] maze, int[] start, int[] destination,
              boolean[][] visited) {
    if (visited[start[0]][start[1]]) return false;
    if (start[0] == destination[0] && start[1] == destination[1]) return true;
    visited[start[0]][start[1]] = true;
    int r = start[1] + 1, l = start[1] - 1, u = start[0] - 1, d = start[0] + 1;
    while (r < maze[0].length && maze[start[0]][r] == 0)  // R
      r++;
    if (dfs(maze, new int[]{start[0], r - 1}, destination, visited))
      return true;
    while (l >= 0 && maze[start[0]][l] == 0)  // L
      l--;
    if (dfs(maze, new int[]{start[0], l + 1}, destination, visited))
      return true;
    while (u >= 0 && maze[u][start[1]] == 0)  // U
      u--;
    if (dfs(maze, new int[]{u + 1, start[1]}, destination, visited))
      return true;
    while (d < maze.length && maze[d][start[1]] == 0)  // D
      d++;
    if (dfs(maze, new int[]{d - 1, start[1]}, destination, visited))
      return true;
    return false;
  }
}
